#pragma once
#ifndef QUEUELI_H
#define QUEUELI_H
template <class T>
class Queue
{
private:
	struct ListNode {
		T element;
		ListNode *next;
		ListNode(const T& p_element, ListNode *p_next = 0) :element(p_element), next(p_next) {}
	};
	ListNode *front;
	ListNode *back;
public:
	Queue();
	~Queue();

	bool isEmpty() const;
	const T &getFront() const;
	void enqueue(const T &x);
	T deque();
	void makeEmpty();
};
template <class T>
Queue<T>::Queue() { front = back = 0; }
template <class T>
Queue<T>::~Queue() { makeEmpty(); }
template <class T>
bool Queue<T>::isEmpty() const { return front == 0; }
template <class T>
const T &Queue<T>::getFront() const { 
	if (isEmpty())
		throw"Queue is empty!";
	else 
		return front->element; 
}
template <class T>
void Queue<T>::enqueue(const T &x) {
	if (isEmpty())
		back = front = new ListNode(x);
	else
		back = back->next = new ListNode(x);
}
template <class T>
T Queue<T>::deque() {
	T frontItem = getFront();
	ListNode *old = front;
	front = front->next;
	delete old;
	return frontItem;
}
template <class T>
void Queue<T>::makeEmpty() {
	while (!isEmpty())
		deque();
}
#endif // !QUEUELI_H
